The procedure for transmitting and receiving information using Reed-Solomon codes for error detection and correction can be described as follows. Information to be transmitted, universally represented as a stream of bits, is divided into small blocks of a certain size m. These small blocks of m bits can be identified with the elements of a mathematical structure known as finite field (or Galois Field) in the sense that there is one-to-one mapping between the set of all possible 2m blocks of m bits and the set of all 2m elements of the Galois Field (GF) of dimension 2m, GF(2m). The Galois field itself can be constructed as the set of all polynomials of degree<m with the coefficients from the “ground” binary field GF(2) whose elements are 0 and 1 and two field operations, addition and multiplication, defined as follows: addition is performed as an “exclusive OR” (XOR) operation on the ordered m-tuple of polynomial coefficients and multiplication is implemented as polynomial multiplication modulo certain “primitive” binary polynomial of degree m as field multiplication, where the “primitive” binary polynomial is irreducible (can not be factored further into a product of binary polynomials of lower degree) and in addition, does not divide any binary polynomial of the form xd−1 for d<2m−1.
One of the most important and common cases is m=8, where each such a block is represented as byte and can be conveniently handled by any kind of computer, so the following discussion is for the case where bytes are the elements of GF(256), with the understanding that “byte” can be an element, or “symbol”, of the Galois field of dimension 2m with m≠8. The primitive polynomial that allows building of GF(256) is p(x)=x8+x4+x3+x2+1.
After setting up the basic units of information (bytes or symbols) and the corresponding Galois Field (GF), information to be transmitted is divided into groups of symbols of equal size k, which is found based upon the desired error correction capability of the code. Each such a group is called “message”. A message is further interpreted as a polynomial M(x) over GF of degree k−1M(x)=m0xk−1+m1xk−2+ . . . +mk−1  (1)whose coefficients mi in the ascending order are information symbols in the order they were obtained from the original stream of bits treated as GF elements. To construct a Reed-Solomon code capable of correcting t errors, a polynomial G(x) of degree 2t, known as a generator polynomial, is defined according to the following formulaG(x)=(x−a2t−1)(x−a2t−2) . . . (x−a1)(x−a0)=x2t+g2t−1+ . . . +g0  (2)where a denotes the so-called “primitive” element of the GF possessing two important (and related) properties: first, it satisfies the equation p(a)=0, and second, as a consequence, all non-zero elements of the GF can be expressed as powers of the primitive element and form an abelian (or commutative) group under the operation of GF multiplication. It is exactly this property that permits creation of an “anti-log” table that establishes a convenient way to perform multiplication of the GF elements using this table.Then the remainder R(x) of the division of message polynomial M(x) multiplied by x2t by the generator polynomial G(x) is found:M(x)x2t=Q(x)*G(x)+R(x),  (3)The remainder is a polynomial of degree 2t−1 and finally, 2t coefficients of this polynomial are used as check symbols which are appended to k message symbols forming a string of k+2t symbols that comprise a “codeword” in systematic form. The length of the codeword should not exceed n−1, the number of non-zero elements in the GF. So the message actually transmitted over a communication channel can be represented as the polynomialM(x)*x2t+R(x)=M(x)*x2t+r2t−1x2t−1+ . . . +r0  (4)where rm are check symbols—redundant symbols that allow detection and correction of up to t errors.
The task of encoding consists, therefore, in performing the division of polynomials whose coefficients are symbols of some GF. A conventional software approach to deal with calculations in the GF is based on using two look-up tables where transformations from the polynomial form of the GF symbols to exponential form and back are stored. This method can be summarized (for our main case of GF(28)) as follows:                1. Symbols (elements of the GF) in the polynomial form are represented as bytes:b=(b7b6b5b4b3b2b1b0).  (5)        2. The sum of the symbols is found as a bitwise XOR operation: f+g=f^g.        3. The primitive element a in polynomial form is represented as a=(00000010), which in polynomial notation corresponds to a(x)=x.        4. Each non-zero symbol s is primitive element a raised to a certain power s=ak. Using polynomial algebra manipulations with binary polynomials, a discrete logarithm table log_table and an exponent table exp_table are pre-calculated to facilitate transformations between exponential (power) and polynomial (byte) representation of (non-zero) elements so thatif ak=b, then k=log_table[b], b=exp_table[k].  (6)        
To multiply GF symbols using these tables, the following chain of operations should be performed assuming operands u and v and result r are in byte form:GFMUL(u,v)=GFMUL(alog—table[u], alog—table[v])=a(log—table[v])%255  (7)r=GFMUL(u,v)=exp_table[(log_table[u]+log_table[v])%255]  (8)where % denotes modulo operation (x %255 is the remainder of the division of x by 255).
It is clear that the speed of calculation of the result of multiplication over GF based on this approach is limited by the fact that multiple access to the tables is needed and the address of the entry into the exponent table should be calculated by addition. In many cases, access through the modified address register requires 2–3 waiting cycles so the total time of one GF multiplication can be 10–12 clock cycles per symbol (byte). This makes software implementation of the Reed-Solomon codes a challenging problem—e.g., in a typical case of (204,188,16) Reed-Solomon code with 188 data bytes and 16 check bytes to encode one codeword 188*16*(10–12)˜=30–36 K cycles are needed, as described below. Thus, for example, for the ADSL application with a rate of transmission of 4 K Symbols/sec, the total consumption of MIPS for only the encoder operation is 120–144 MIPS, which is prohibitively high.